Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:

Given binary tree [1,null,2,3],

  1.    1
  2.     \
  3.      2
  4.     /
  5.    3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public List<Integer> inorderTraversal(TreeNode root) {
  12.     List<Integer> list = new ArrayList<>();
  14.     TreeNode curr = root;
  15.     Stack<TreeNode> stack = new Stack<>();
  17.     while (!stack.isEmpty() || curr != null) {
  18.       if (curr != null) {
  19.         stack.push(curr);
  20.         curr = curr.left;
  21.       } else {
  22.         curr = stack.pop();
  23.         list.add(curr.val);
  24.         curr = curr.right;
  25.       }
  26.     }
  28.     return list;
  29.   }
  30. }